// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 *
 * @author: yanking
 * Create time: 2022-03-08 17:06
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.LeetCodeT.TREE;

import com.DataStruct.Tree.TwoBinaryTree.TreeNode;
import com.DataStruct.Tree.TwoBinaryTree.Utils;
import org.junit.jupiter.api.Test;


@SuppressWarnings("ALL")
public class MinDiffInBST {
    int[] min = new int[2];

    /**
     * 使用二叉树的中序遍历实现对排序二叉树中任意两个节点最小差值获取
     */
    public int minDiffInBST(TreeNode root) {
        if (root == null || root.left == null && root.right == null) {
            return -1;
        }
        min[0] = Integer.MAX_VALUE;
        min[1] = Integer.MIN_VALUE;
        midSearch(root);
        return min[0];
    }

    /**
     * 实现二叉树的中序遍历，通过保持最小的两个节点之间的差值
     *
     * @param root 根节点
     */
    private void midSearch(TreeNode root) {
        if (root == null) {
            return;
        }
        if (root.left != null) {
            midSearch(root.left);
        }
        min[0] = Math.min(min[0], root.val - min[1]);
        min[1] = root.val;
        if (root.right != null) {
            midSearch(root.right);
        }
    }

    @Test
    public void shout() {
        Utils utils = new Utils();
        int[] nodes = {4, 2, 6, 1, 3};
        TreeNode<Integer> root = utils.constructTreeBySequence(nodes);
        System.out.println(minDiffInBST(root));
    }


}
